package lanQiaoBei.搜索与图论.bfs;

import java.io.*;
import java.math.*;
import java.util.*;

/*图中节点的层次
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环。

所有边的长度都是 1，点的编号为 1∼n。

请你求出 1 号点到 n 号点的最短距离，如果从 1 号点无法走到 n 号点，输出 −1。

输入格式
第一行包含两个整数 n 和 m。

接下来 m 行，每行包含两个整数 a 和 b，表示存在一条从 a 走到 b 的长度为 1 的边。

输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。

数据范围
1≤n,m≤105
输入样例：
4 5
1 2
2 3
3 4
1 1
1 1
输出样例：
3
* */
public class P2 {
       static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
       final static int N=100010;
       static int h[]=new int[N],e[]=new int[N],ne[]=new int[N],ds[]=new int[N],idx,n,m;
       
       static void add(int a,int b){
    	      e[idx]=b;ne[idx]=h[a];h[a]=idx++;
       }
       static void bfs(){
    	      int q[]=new int[N],hh=0,tt=-1;
    	      q[++tt]=1;
    	      ds[1]=0;
    	      while(hh<=tt){
    	    	  int t=q[hh++];
    	    	  for(int i=h[t];i!=-1;i=ne[i]){
    	    		  int j=e[i];
    	    		  if(ds[j]==-1){
    	    			  ds[j]=ds[t]+1;
    	    			  q[++tt]=j;
    	    		  }
    	    	  }
    	      }
       }
       public static void main(String[] ss) throws IOException {
		      ss=br.readLine().split(" ");
		      n=Integer.parseInt(ss[0]);m=Integer.parseInt(ss[1]);
		      Arrays.fill(h,-1);
              Arrays.fill(ds, -1);
		      while(m-->0){
		    	   ss=br.readLine().split(" ");
		    	   int a=Integer.parseInt(ss[0]),b=Integer.parseInt(ss[1]);
		    	   add(a,b);
		      }
		      bfs();
		      System.out.print(ds[n]);
		      
	}
}
